A telecommunications network typically comprises a group of switching offices interconnected by trunk groups. Each office may comprise a switch operating under the control of a stored program processor for establishing connections between incoming and outgoing trunk groups. Setting up a call in the network typically involves establishing a connection between an originating switching office and a destination switching office. Depending on the state of the network (i.e., the level of congestion in particular trunk groups) the route from the originating switching office to the destination switching office may be direct, or it may be a multi-hop route, passing through one or more intermediate switching offices.
Initially routing in the U.S. public telephone network was handled by human operators. Later, advances in electromechanical, common control, switch technology permitted replacement of the human operators with automated routing. The resulting problems with network congestion were addressed in stored program controlled switching machines such as the #4 ESS and through the use of more sophisticated routing strategies to be implemented by software within the switching offices. Thus, the routing algorithms became more flexible (e.g., capable of changing with the time of day) and more accessible to modification. In addition, switching office machines could be used to collect data about the state of the network and implement internal overload controls. In the 1970's improvements in communications technologies in the form of common channel signaling helped alleviate overload problems by reducing the holding time of network resources in failing call attempts and generally permitting a more flexible and rapid dissemination of information about call attempts through the network. Various strategies have been used by central switching offices to chose particular routes for calls in the telephone network. One such strategy is known as Dynamic Non-Hierarchical Routing (DNHR) (see for example G. R. Ash et al "Design and Optimization of Networks with Dynamic Routing" Bell System Technical Journal Vol 60, pp 1787-1820, 0ctober 1981). DNHR is preplanned routing, defined statically at the time the network is engineered. More particularly, in DNHR each switching office maintains a list of possible routes between it and other switching offices in the network. Thus, when switching office A wants to establish a connection with switching office B, switching office A will test the list of possible routes between switching office A and switching office B, until an available route is found. If none of the routes in the list is available, the call will be blocked. The list of routes between any pair of switching offices, such as switching offices A and B mentioned above, is ordered so that network resources are used most efficiently. For example, first the direct route between switching offices A and B is tested, then routes having one intermediate switching office, etc.
The ordering of routes in the list may change at different times in the day to reflect different network conditions. In this sense, the DNHR scheme is dynamic. However, the lists of routes maintained in each central switching office and changes in the lists at particular times are statically engineered into the network when it is built. Thus, the DNHR scheme is not dynamic in the sense that information about the state of the network is not dynamically provided to each switching office so that routing decisions can be made based on the actual state of the network at the time of call set-up.
Other more sophisticated routing schemes have been suggested in which some global information is maintained about the state of the network. (See for example B. Akselrod et al "A Simulation Study of Advances Routing Methods in a Multipriority Telephone Network" IEEE Trans-Systems, Man and Cybernetics Vol, SMC 15, No. 6, November-December 1985, K. Mase et al "Network Control Using Traffic Databases" Proc., Int. Conf. on Communications, 1982, E. Szybicki et al, "Routing in Local Telephone Networks. Performance of proposed Call Algorithms" Ninth Int. Teletraffic Congress Torremolinos, Spain October 1979, G. R. Ash "Use of a Trunk Status Map for Real Time DNHR" Proc. Eleventh Int. Teletraffic Congress Kyoto, September 1985) For example, to complete a call, routes are tested in an order determined by dynamically varying probabilities calculated using the estimated global information about the state of the network. Databases containing the estimated global information may be maintained centrally or in a distributed manner. Unless these databases are updated frequently, so that they can track the network state very closely, it is possible that these algorithms may actually perform worse than the statically defined routing scheme discussed above.
In addition, in all of the above schemes, routes are tried sequentially and some trunks in a route may be held by a call, while other trunks comprising the route are being obtained. Thus, a call, which eventually gets blocked due to the unavailability of a particular trunk in a route, may have held onto other trunks and switching resources unnecessarily. This may be particularly significant during overload situations.
One other routing scheme worth mentioning evaluates future blocking estimate factors for various routes based on past and present network states, as well as estimates or future traffic blocking (see Krishnan and Ott U.S. Pat. No. 4,704,724, issued Nov. 3, 1987 filed on Dec. 5, 1985 and assigned to the Assignee hereof). These factors serve to determine which route to use and also indicate when calls should be blocked even though a route may be available, since blocking the call may be the best strategy to optimize overall network performance.
It is an object of the present invention to provide an architecture for controlling the allocation of network resources, so that routing decisions can be made efficiently. More particularly, it is an object of the present invention to provide a network control architecture for controlling the allocation of network resources and which permits routing decisions to be based on a substantially exact knowledge of the state of the network, at the time the routing decision is made.